package main.leetcode.offer.secondround.from03to50;

import java.util.Comparator;
import java.util.PriorityQueue;

/** 41.数据流中的中位数 */
public class ex41 {
    private PriorityQueue<Integer> maxHeap;
    private PriorityQueue<Integer> minHeap;
    /** initialize your data structure here. */
    public ex41() {
        maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
        minHeap = new PriorityQueue<>();
    }

    public void addNum(int num) {
        // 保证两个堆分布均匀
        maxHeap.add(num);
        minHeap.add(maxHeap.poll());
        // 大顶堆为空
        if (maxHeap.size() < minHeap.size()) {
            maxHeap.add(minHeap.poll());
        }
    }

    public double findMedian() {
        // 容量相同 => 偶数个数字
        if (maxHeap.size() == minHeap.size()) {
            return (double) (maxHeap.peek() + minHeap.peek()) / 2;
        }
        return (double) maxHeap.peek();
    }
}
